This invention relates to the field of image processing. More specifically, the invention relates to a system and method for processing and matching fingerprint images.
There exist systems for accomplishing automatic authentication or identification of a person using his/her fingerprint. A fingerprint of a person comprises a distinctive and unique ridge pattern structure. For authentication or identification purposes, this ridge pattern structure can be characterized by endings and bifurcations of the individual ridges. These features are popularly known as minutiae.
An example of portion of a fingerprint is shown in FIG. 1A. The minutiae for the fingerprint shown in FIG. 1A are shown in FIG. 1B as being enclosed by xe2x80x9cboxes.xe2x80x9d For example, box 101B shows a bifurcation minutiae of a bifurcated ridge 101A and box 103B shows a ridge ending minutiae of ridge 103A. Note that minutiae on the ridges in fingerprints have directions (also called orientations) 105 associated with them. The direction 113B of a minutiae at a ridge end 103B is the direction in which the end of the ridge points. The direction 111B of a bifurcation minutiae 101B is the direction in which the bifurcated ridge points. Minutiae also have locations which are the positions, with respect to some coordinate system, of the minutiae on the fingerprint.
FIG. 2 is a flow chart showing the steps generally performed by a typical prior art system 200.
In step 210, the image is acquired. This acquisition of the image could either be through a CCD camera and framegrabber interface or through a document scanner communicating with the primary computing equipment.
Once the image is acquired into the computer memory or onto disk, relevant minutia features are extracted (220). Not all of the features thus extracted are reliable; some of the unreliable features are optionally edited or pruned (step 230), e.g., manually. The resultant reliable features are used for matching the fingers (step 240).
The fingerprint feature extraction 220, pruning 230, and matching system 240 constitute the primary backbone 250 of a typical minutiae-based automatic fingerprint identification systems (AFIS). The matching results are typically verified by a human expert (step 260). The verification may also be performed automatically. The following reference describes examples of the state of the prior art for feature extraction:
Nalini K. Ratha and Shaoyun Chen and Anil K. Jain,
Adaptive flow orientation based feature extraction in fingerprint images, Journal of Pattern Recognition, vol. 28, no. 11, pp. 1657-1672, November, 1995.
This reference is herein incorporated by reference in its entirety.
FIG. 3A is a flow chart showing the prior art steps performed by a feature extraction process 220 that are similar to some of the feature extraction methods proposed by Ratha, Jain, and Chen in the article incorporated above.
It is often not desirable to directly use the input fingerprint image for feature extraction. The fingerprint image might need an enhancement or preprocessing before one could further extract minutiae. Typically, a smoothing process is employed to reduce the pixel-wise noise (step 305).
After the preprocessing stages, prior art systems find the directions of the ridge flow (step 310). The next important step in the processing is finding the exact location of the finger in the image. To accomplish this, a process referred to as the foreground/background segmentation (step 315) separates the finger part of the image from the background part of the image. Once the finger part is localized, i.e., segmented to define its location, the next step is to extract the ridges from the finger image (step 320). The ridges thus extracted are thick and might contain some noisy artifacts which do not correspond to any meaningful structures on the finger. These small structures, i.e., the noisy artifacts, can be safely removed and the longer structures are smoothed (step 325). The longer structures are thinned to one-pixel width and then processed to remove any other artifacts using morphological operators (step 330). The locations and orientations of ridge endings and bifurcations are then extracted from the thinned structures (step 335) to obtain the minutiae. In some systems, a xe2x80x9ccleanupxe2x80x9d or postprocessing 340 is performed. Here undesirable minutiae are removed based on certain criteria.
One of the prevalent methods of fingerprint authentication and identification methods is based on minutiae features. These systems need to process the fingerprint images to obtain accurate and reliable minutiae features to effectively determine the identity of a person.
The following reference describes examples of the state of the prior art fingerprint matcher:
N. Ratha, K. Karu, S. Chen and A. K. Jain, A Real-time Matching System for Large Fingerprint Database, IEEE Transactions on Pattern Analysis and Machine Intelligence, Volume 18, Number 8, pages 799-813, 1996.
This reference is herein incorporated by reference in its entirety.
Given two (input and template) sets of features originating from two fingerprints, the objective of the feature matching system is to determine whether or not the prints represent the same finger. FIG. 3B is a flow chart showing the prior art steps performed by a typical feature matching system 240 that is similar to the feature matching system proposed by Ratha, Karu, Chen, and Jain in the article incorporated above.
A minutiae in the input fingerprint and a minutiae in the template fingerprint are said to be corresponding if they represent the identical minutiae scanned from the same finger. An alignment estimation method based on Generalized Hough Transform (as in above cited Ratha et al. reference) estimates the parameters of the overall rotation, scaling and translation between the features of the input and template fingerprint (350). In step 360 the input fingerprint features are aligned with the template fingerprint using the rotation, translation, and scaling parameters estimated in step 350. In step 370, the aligned features of the input fingerprint features are matched with the features of the template fingerprint features. The matching consists of counting the number of features in the aligned input fingerprint representation for which there exists a corresponding consistent feature in the template fingerprint representation. The verification of a corresponding feature is performed as follows: for each feature in the aligned input fingerprint feature, the matcher determines whether there is a consistent template fingerprint feature in its rectangular neighborhood whose size is predetermined. Normalizer 380 takes the matching score generated by the matcher and computes a normalized matching score. The higher the normalized score, the higher the likelihood that the test and template fingerprints are the scans of the same finger.
Determining whether two representations of a finger extracted from its two impressions, scanned at times possibly separated by a long duration of time, are indeed representing the same finger, is an extremely difficult problem. This difficulty can be attributed to two primary reasons. First, if the test and template representations are indeed matched (also referred to as mated) pairs, the feature correspondence between the test and template minutiae in the two representations is not known. Secondly, the imaging system presents a number of peculiar and challenging situations some of which are unique to the fingerprint image capture scenario:
(i) Inconsistent contact: The act of sensing distorts the finger. Determined by the pressure and contact of the finger on the glass platen, the three-dimensional surface of the finger gets mapped onto the two-dimensional surface of the glass platen. Typically, this mapping function is uncontrolled and results in different inconsistently mapped fingerprint images across the impressions.
(ii) Non-uniform contact: The ridge structure of a finger would be completely captured if ridges of the part of the finger being imaged are in complete optical contact with the glass platen. However, the dryness of the skin, skin disease, sweat, dirt, humidity in the air all confound the situation resulting in a non-ideal contact situation: some parts of the ridges may not come in complete contact with the platen and regions representing some valleys may come in contact with the glass platen. This results in xe2x80x9cnoisyxe2x80x9d low contrast images, leading to either spurious minutiae or missing minutiae.
(iii) Irreproducible contact: Manual labor, accidents etc. inflict injuries to the finger, thereby, changing the ridge structure of the finger either permanently or semi-permanently. This may introduce additional spurious minutiae.
(iv) Feature extraction artifacts: The feature extraction algorithm is imperfect and introduces measurement errors. Various image processing operations might introduce inconsistent biases to perturb the location and orientation estimates of the reported minutiae from their grayscale counterparts.
(vi) The act of sensing itself adds noise to the image. For example, residues are leftover from the previous fingerprint capture. A typical imaging system distorts the image of the object being sensed due to imperfect imaging conditions. In the frustrated total internal reflection (FTIR) sensing scheme, for example, there is a geometric distortion because the image plane is not parallel to the glass platen.
In light of the operational environments mentioned above, the design of prior art matching algorithms 240 use models that have one or more of the following constraints or assumptions:
1. The finger may be placed at different locations on the glass platen resulting in a (global) translation of the minutiae from the test representation from those in the template representation.
2. The finger may be placed in different orientations on the glass platen resulting in a (global) rotation of the minutiae from the test representation from that of the template representation.
3. The finger may exert a different (average) downward normal pressure on the glass platen resulting in a (global) spatial scaling of the minutiae from the test representation from those in the template representation. For best matching results, two impressions of a fingerprint obtained by applying different downward normal pressure need to be scaled by an appropriate scaling factor.
4. The finger may exert a different (average) shear force on the glass platen resulting in a (global) shear transformation (characterized by a shear direction and magnitude) of the minutiae from the test representation from those in the template representation.
5. Spurious minutiae may be present in both the template as well as the test representations.
6. Genuine minutiae may be absent in the template or test representations.
7. Minutiae may be locally perturbed from their xe2x80x9ctruexe2x80x9d location and the perturbation may be different for each individual minutiae. (Further, the magnitude of such perturbation is assumed to be small and within a fixed number of pixels.)
8. The individual perturbations among the corresponding minutiae could be relatively large (with respect to ridge spacings) but the perturbations among pairs of the minutiae may be spatially linear. The prior art does not effectively use this information.
9. The individual perturbations among the corresponding minutiae could be relatively large (with respect to ridge spacings) but the perturbations among pairs of the minutiae may be spatially non-linear. The prior art does not recognize or effectively handle this type of situation.
10. Only a (ridge) connectivity preserving transformation could characterize the relationship between the test and template representations.
Prior art matchers 240 relying on one or more of these assumptions have a wide spectrum of behavior. At the one end of the spectrum, the xe2x80x9cEuclideanxe2x80x9d matchers allow only rigid transformations (assumptions 1, 2, and 3) among the test and template representations. At the other extreme, xe2x80x9ctopologicalxe2x80x9d matchers (e.g., Sparrow et al.) may allow the most general transformations including, say, order reversals. (Order reversal means that a set of minutiae in the test representation are in totally different spatial order with respect to their correspondences in the template representation).
The choice of assumptions often represents verification performance trade-offs. Only a highly constrained system (one that obtains exact and high quality fingerprints) or systems that do not have to give very accurate matches may use only a few of the assumptions above. For examples, a number of the matchers in the literature assume similarity transformation (assumptions 1, 2, and 3); they tolerate both spurious minutiae as well as missing genuine minutiae. Alternative prior art systems like xe2x80x9cElasticxe2x80x9d matchers (e.g., Ratha et al) use assumptions 1, 2, 3, 5, 6, and 7) accommodate a small bounded local perturbation of minutiae from their true location but cannot handle large displacements of the minutiae from their true locations (assumptions 4 and 8).
FIG. 4 illustrates a typical situation of aligned ridge structures of two fingerprints 401 and 402 scanned from the same finger (also called as a mated pair). The ridges of the 401 print are shown in solid lines and those of 402 are shown as dashed lines. Note that the best alignment in one part (bottom left 410) of the image may result in a large amount of displacements between the corresponding minutiae in the other regions (top middle 420). Consequently, the corresponding minutiae in the two fingerprints in the region 410, e.g., 450 and 460, are relatively closer and the corresponding minutiae in the two fingerprints in the region 420, e.g., 430 and 440, are separated 435 farther apart. In addition, observe that the distortion is non-linear: given distortions (e.g., 435 and 455) at two arbitrary locations on the finger, it is not possible to predict the distortion, e.g. 436, at all the intervening points on the between the respective lines joining the two points. Also, note that typically the spatial relationship of the two minutiae (e.g., 440 is top right of 450 in the fingerprint 401; and 430 is top right of 460 in the print 402) in each finger has remained same despite the large distortion. In our opinion, a good matcher needs to accommodate not only global similarity transformations (assumptions 1, 2, and 3), but also shear transformation (assumption 4), linear (assumption 8) and non-linear (assumption 9) differential distortions. In our experience, assumption 10 is too general a model to characterize the impressions of a finger and its inclusion into the matcher design may compromise efficiency and discriminatory power of the matcher. In addition, the matchers based on such assumptions need to use connectivity information which is notoriously difficult to extract from the fingerprint images of poor quality.
An object of this invention is an improved image processing system.
An object of this invention is a system and method for deriving a string-based representation of an image.
An object of this invention is a system and method for deriving a string-based representation of a fingerprint image.
The invention is a system and method for deriving a single dimensional (one-dimensional) representation for a two-dimensional pattern of lines, e.g. a fingerprint, by creating a one-dimensional (string) representation of one or more points (e.g., minutiae) and the respective attributes of each point therein. A landmark point is selected from the two-dimensional image, preferably from the set of points to be represented in single dimension. The relationships of each of the points with reference to the landmark determines a linear order for the points and the attributes associated with each point. (Note that pattern and fingerprint, line and fingerprint ridges, and points and minutiae will be used interchangably without loss of generality.)